package com.leetcode.No0895;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

/**
 * @program: FreqStack
 * @description: 最大频率栈
 * @author: Wang Zhihua
 * @date: 2022-12-02
 */
public class FreqStack2 {

    // value -> 频率
    private Map<Integer, Integer> freqMap;
    // 频率 -> 频率栈<value>
    private Map<Integer, Deque<Integer>> groupMap;
    private int maxFreq;

    public FreqStack2() {
        freqMap = new HashMap<>();
        groupMap = new HashMap<>();
        maxFreq = 0;
    }

    public void push(int val) {
        Integer freqNum = freqMap.getOrDefault(val, 0);
        ++freqNum;
        freqMap.put(val, freqNum);
        Deque<Integer> deque = groupMap.getOrDefault(freqNum, new ArrayDeque<>());
        deque.push(val);
        groupMap.put(freqNum, deque);
        maxFreq = Math.max(maxFreq, freqNum);
    }

    public int pop() {
        Deque<Integer> deque = groupMap.get(maxFreq);
        Integer value = deque.pop();
        freqMap.put(value, freqMap.get(value) - 1);
        if (deque.isEmpty()) {
            --maxFreq;
        }
        return value;
    }

    @Test
    public void test01() {
        FreqStack2 freqStack = new FreqStack2();
        freqStack.push(5);
        freqStack.push(7);
        freqStack.push(5);
        freqStack.push(7);
        freqStack.push(4);
        freqStack.push(5);
        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
    }

    @Test
    public void test02() {
        FreqStack2 freqStack = new FreqStack2();
        freqStack.push(4);
        freqStack.push(0);
        freqStack.push(9);
        freqStack.push(3);
        freqStack.push(4);
        freqStack.push(2);
        System.out.println(freqStack.pop());
        freqStack.push(6);
        System.out.println(freqStack.pop());
        freqStack.push(1);
        System.out.println(freqStack.pop());
        freqStack.push(1);
        System.out.println(freqStack.pop());
        freqStack.push(4);
        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
    }

}
